package com.github.yangyishe.p100;

/**
 * 寻找两个正序数组的中位数
 * https://leetcode.cn/problems/median-of-two-sorted-arrays/
 * todo 时间复杂度是O(m+n), 但效率仍然超过了100%
 *
 * The type Problem 4.
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 *
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 *
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 *
 *
 *
 *
 * 提示：
 *
 * nums1.length == m
 * nums2.length == n
 * 0 <= m <= 1000
 * 0 <= n <= 1000
 * 1 <= m + n <= 2000
 * -106 <= nums1[i], nums2[i] <= 106
 */
public class Problem04 {
    public static void main(String[] args) {
        Problem04 problem04 = new Problem04();
        int[] nums1={5};
        int[] nums2={1,2,3,4,6};
        double v = problem04.findMedianSortedArrays(nums1, nums2);
        System.out.println(v);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//        int minIndex1=0;
//        int minIndex2=0;
        if (nums2.length==0) {
            return nums1.length%2!=0?nums1[nums1.length/2]: (double) (nums1[nums1.length / 2] + nums1[nums1.length / 2 - 1]) /2;
        }
        if (nums1.length==0) {
            return nums2.length%2!=0?nums2[nums2.length/2]: (double) (nums2[nums2.length / 2] + nums2[nums2.length / 2 - 1]) /2;
        }

        int maxIndex1=nums1.length-1;
        int maxIndex2= nums2.length-1;

        boolean isDouble= (nums1.length+nums2.length)%2==0;

        int postSize= (nums1.length+nums2.length)/2-(isDouble?1:0);
//        boolean emptyNums1=false;
//        boolean emptyNums2=false;
        while (postSize != 0) {

            int max1 = nums1[maxIndex1];
            int max2 = nums2[maxIndex2];
            if (max1 > max2) {
                int reduceCount;
                int halfArrSize = (maxIndex1 ) / 2;
                if (halfArrSize == 0) {
                    reduceCount = 1;
//                    emptyNums1 = true;
                } else {
                    reduceCount = halfArrSize;
                }
                reduceCount = Math.min(postSize, reduceCount);
                postSize -= reduceCount;
                maxIndex1 -= reduceCount;
                if(maxIndex1<0){
                    maxIndex2-=postSize;
                    postSize=0;
                }
            } else {
                int reduceCount;
                int halfArrSize = (maxIndex2 ) / 2;
                if (halfArrSize == 0) {
                    reduceCount = 1;
//                    emptyNums2 = true;
                } else {
                    reduceCount = halfArrSize;
                }
                reduceCount = Math.min(reduceCount, postSize);
                postSize -= reduceCount;
                maxIndex2 -= reduceCount;
                if(maxIndex2<0){
                    maxIndex1-=postSize;
                    postSize=0;
                }
            }

        }

        // calc avg by last 1 or 2 nums
        if (isDouble) {
            double sum;
//            if (emptyNums2) {
//                sum = nums1[maxIndex1-1] + nums1[maxIndex1];
//            }else if(emptyNums1){
//                sum=nums2[maxIndex2-1]+nums2[maxIndex2];
//            }else{
//                int firstMax=Math.max(nums1[maxIndex1],nums2[maxIndex2]);
//                int secondMax=Math.min(nums1[maxIndex1],nums2[maxIndex2]);
//                if (maxIndex1>=1) {
//                    secondMax=Math.max(nums1[maxIndex1-1],secondMax);
//                }
//                if (maxIndex2>=1) {
//                    secondMax=Math.max(nums2[maxIndex2-1],secondMax);
//                }
//                sum=firstMax+secondMax;
//            }
            if(maxIndex1<0){
                return (double)(nums2[maxIndex2-1]+nums2[maxIndex2])/2;
            }
            if(maxIndex2<0){
                return (double)(nums1[maxIndex1-1]+nums1[maxIndex1])/2;
            }
            int firstMax=Math.max(nums1[maxIndex1],nums2[maxIndex2]);
            int secondMax=Math.min(nums1[maxIndex1],nums2[maxIndex2]);
            if (maxIndex1>=1) {
                secondMax=Math.max(nums1[maxIndex1-1],secondMax);
            }
            if (maxIndex2>=1) {
                secondMax=Math.max(nums2[maxIndex2-1],secondMax);
            }
            sum=firstMax+secondMax;
            return sum/2;
        }else{
//            if (emptyNums1) {
//                return nums2[maxIndex2];
//            }else if(emptyNums2){
//                return nums1[maxIndex1];
//            }else{
//                return Math.max(nums1[maxIndex1],nums2[maxIndex2]);
//            }
            if(maxIndex1<0){
                return nums2[maxIndex2];
            }
            if(maxIndex2<0){
                return nums1[maxIndex1];
            }
            return Math.max(nums1[maxIndex1],nums2[maxIndex2]);
        }

    }

    /**
     * 时间复杂度O(n)
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArraysOn(int[] nums1, int[] nums2) {
        int minIndex1=0;
        int minIndex2=0;

        int maxIndex1=nums1.length-1;
        int maxIndex2= nums2.length-1;

        boolean isDouble= (nums1.length+nums2.length)%2==0;

        while(true){
            int size1 = maxIndex1 - minIndex1+1;
            int size2=maxIndex2-minIndex2+1;
            if (size1+size2<=2) {
                break;
            }

            int min1=nums1[minIndex1];
            int min2=nums2[minIndex2];
            if (min1<min2) {
                minIndex1++;
            }else{
                minIndex2++;
            }

            int max1=nums1[maxIndex1];
            int max2=nums2[maxIndex2];
            if (max1>max2) {
                maxIndex1--;
            }else{
                maxIndex2--;
            }

        }

        // calc avg by last 1 or 2 nums
        if (isDouble) {
            double sum;
            if (maxIndex1-minIndex1==1) {
                sum = nums1[minIndex1] + nums1[maxIndex1];
            }else if(maxIndex1==minIndex1){
                sum=nums1[minIndex1]+nums2[minIndex2];
            }else{
                sum=nums2[minIndex2]+nums2[maxIndex2];
            }
            return sum/2;
        }else{
            if (minIndex1>maxIndex1) {
                return nums2[minIndex2];
            }else{
                return nums1[minIndex1];
            }
        }

    }
}
